#include <iostream>
#include <vector>

using namespace std;

// 二分搜索，在非降序序列a中搜索x
int binarySearch(vector<int>& a, int x) {
    int left = 0, right = a.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (x > a[mid])
            left = mid + 1;  // x位于mid右边，调整左边界
        else if (x < a[mid])
            right = mid - 1;  // x位于mid左边，调整右边界
        else
            return mid;  // 找到x，返回当前位置
    }
    return -1;  // 搜索完毕，未找到x，返回-1
}

// 二分搜索 - 常规解法（递归）
int search(vector<int>& nums, int target, int start, int end) {
    if (start > end) return -1;
    if (start == end) return nums[start] == target? start : -1;
    int mid = start + (end - start) / 2;
    if (nums[mid] == target) return mid;
    else if (target < nums[mid])
        return search(nums, target, start, mid - 1);
    else  // if target > nums[mid] 
        return search(nums, target, mid + 1, end);
}

// 力扣704 - 对应功能函数，这里使用常规（简化版）方法
int search(vector<int>& nums, int target) {
    return search(nums, target, 0, nums.size() - 1);
}

// 下界模板
// 下界的定义：数组中大于等于target的第一个元素下标位置
// 当target存在多个时，下界取到最左边的元素
// 当target不存在时，下界表示target在排序数组中的插入位置
int lowerBound(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = (left + right) / 2;  // 注意这里不要记错成上界模板的(left+right+1)/2，否则同样会掉入死循环陷阱
        if (nums[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}

// 上界模板
// 上界的定义：数组中小于等于target的最后一个元素下标位置
// 当target存在多个时，上界取到最右边的元素
// 当target不存在时，上界表示target在排序数组中的插入位置之前的位置
int upperBound(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = (left + right + 1) / 2;  // 小心死循环陷阱，这里记得+1
        if (nums[mid] > target)
            right = mid - 1;
        else
            left = mid;
    }
    return left;
}

// 演示：通过上界和下界求目标值的总个数
void test() {
    vector<int> a = { 1, 2, 3, 3, 3, 4, 5, 6 };
    int t = 3;
    int lb = lowerBound(a, t);
    int ub = upperBound(a, t);
    cout << "数组搜索的下界是" << lb << ", 上界是" << ub << ", 目标元素总共有" << (ub - lb + 1) << "个" << endl;
}

int main() {
    test();
    return 0;
}